Many current communication systems are based on Orthogonal Frequency Division Multiplexing (OFDM) and related technologies. The Fourier transformation of a signal from time domain into frequency domain and vice versa is one of the most important processing modules in such systems. The fast Fourier transform (FFT) is an efficient algorithm to compute a DFT and its inverse. In general, FFTs are of great importance to a wide variety of other applications as well, e.g., digital signal processing for solving partial differential equations, algorithms for quickly multiplying large integers, and the like.
A limitation of FFT is that it can only process data vectors which have a length in the form of 2x, where x is a positive integer. However, latest communication standards, e.g. EUTRAN/LTE (Enhanced Universal Mobile Telecommunications System Terrestrial Radio Access Network/Long Term Evolution) use Fourier transformation of signals with a vector length other than 2x, which requires DFT. Compared with FFT, a straight forward implementation of the DFT algorithm would result in unacceptable processing time of the order n2.
The U.S. Pat. No. 5,233,551 discloses a radix-12 DFT/FFT building block using classic FFT rules, which first divides the input values into six groups of two values for the first tier which contains six multiplier-free radix-2 DFT processing elements. The output of the first tier (12 complex values) is then divided into two groups of six values and used as input for the second tier which contains two multiplier-free radix-6 DFT processing element. As a consequence, complex twiddle factor multipliers and ancillary address reduce to a total of 144 real adds required to perform the entire complex 12-point FFT.